// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-03-01 21:27
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

public class MaxProfit2 {
    // 只能买一个股票，得到给定数组所能给的最大利益
    // 使用双指针，记录从左到当前位置的最小值和从右到当前位置的最大值
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] leftMin = new int[n];
        int[] rightMax = new int[n];
        int max = 0;
        leftMin[0] = prices[0];
        rightMax[n - 1] = prices[n - 1];
        for (int i = 1; i < n; i++) {
            int price = prices[i];
            leftMin[i] = Math.min(leftMin[i - 1], price);
        }
        for (int i = n - 2; i >= 0; i--) {
            int price = prices[i];
            rightMax[i] = Math.max(rightMax[i + 1], price);
        }
        for (int i = 0; i < n; i++) {
            max = Math.max(max, rightMax[i] - leftMin[i]);
        }
        return max;
    }


    @Test
    public void shout00() {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices));
    }
}
